import Graph from '../../data-structures/graph';
import Queue from '../../data-structures/queue';

enum Colors {
    WHITE = 0, // 没被访问过
    GREY = 1, // 被访问过一次，处于待第二次访问状态
    BLACK = 2, // 完全探索完（它的邻接顶点都被访问了一次）
}

/**
 * 初始化图里所有顶点的颜色，白色（没被访问过）
 */
const initializeColor = (vertices: Array<string | number>): { [key: string]: Colors } => {
    const color: { [key: string]: Colors } = {};
    for (let i = 0, vl = vertices.length; i < vl; i ++) {
        color[vertices[i]] = Colors.WHITE;
    }
    return color;
};

/**
 * 广度优先遍历(BFS)，并在每个点遍历完后回调
 * @param graph 图（无向图和有向图都可以）
 * @param startVertex 从图里的哪一个顶点开始遍历
 * @param callBack 一个顶点被完全探索完时的回调
 */
export const breadthFirstSearch = (graph: Graph, startVertex: string | number = null, callBack: Function = null) => {
    const vertices: Array<string | number> = graph.getVertices(); // 所有顶点
    const adjList: Map<string | number, Array<string | number>> = graph.getAdjList(); // 顶点与邻接顶点的关系
    const color: { [key: string]: Colors } = initializeColor(vertices); // 初始化所有顶点的颜色，默认都是白色（没被访问过）

    if (startVertex != null && vertices.includes(startVertex)) { // 开始点存在并且是该图里的顶点
        breadthFirstSearchVisit(startVertex, adjList, color, callBack);
    } else { // 没有开始点就从vertices的0下标开始
        for (let i = 0, vl = vertices.length; i < vl; i ++) {
            if (color[vertices[i]] === Colors.WHITE) { // 未访问的
                breadthFirstSearchVisit(vertices[i], adjList, color, callBack);
            }
        }
    }
};

const breadthFirstSearchVisit = (
    startVertex: string | number = null,
    adjList: Map<string | number, Array<string | number>>,
    color: { [key: string]: Colors },
    callBack: Function = null,
) => {
    const queue: Queue<string | number> = new Queue<string | number>(); // 待访问列表是队列结构的
    color[startVertex] = Colors.GREY; // 开始点只会被访问一次，所以要事先置为灰色，后面被访问完就置为黑色
    queue.enqueue(startVertex); // 开始点

    while (!queue.isEmpty()) { // 直到队列为空才结束
        const u: string | number = queue.dequeue(); // 队列最前端取一个，追踪这个顶点，即第二次访问
        const neighbors: Array<string | number> = adjList.get(u); // 它所有邻接顶点
        for (let i = 0, nl = neighbors.length; i < nl; i ++) { // 遍历所有邻接顶点
            const w: string | number = neighbors[i];
            if (color[w] === Colors.WHITE) { // 当前邻接顶点是白色（没被访问过）才被加到待访问列表
                color[w] = Colors.GREY; // 白色变为灰色，被访问一次
                queue.enqueue(w); // 入队列（队列尾部），等待第二次访问
            }
        }
        color[u] = Colors.BLACK; // 完全被探索完，变为黑色
        if (callBack) { // 完全被探索完就回调
            callBack(u);
        }
    }
};

/**
 * 使用广度优先遍历图，得出每个点到开始点的最短距离，还有他们之间的回溯点（具体路径）
 */
export const bfs = (graph: Graph, startVertex: string | number) => {
    const vertices: Array<string | number> = graph.getVertices(); // 所有顶点
    const adjList: Map<string | number, Array<string | number>> = graph.getAdjList(); // 顶点与邻接顶点的关系
    const color: { [key: string]: Colors } = initializeColor(vertices); // 初始化所有顶点的颜色，默认都是白色（没被访问过）

    const distances: { [key: string]: number } = {}; // 距离
    const predecessors: { [key: string]: string | number } = {}; // 回溯顶点

    // 初始化距离和回溯点
    for (let i = 0, vl = vertices.length; i < vl; i ++) {
        distances[vertices[i]] = 0;
        predecessors[vertices[i]] = null;
    }

    if (startVertex == null || !vertices.includes(startVertex)) { // 开始点不存在或者不是该图里的顶点
        return undefined; // 没有开始点，就无法算出距离
    } else { // 没有开始点就从vertices的0下标开始
        bfsVisit(startVertex, adjList, color, distances, predecessors);
    }
    return { distances, predecessors }; // 返回每个点到开始点的距离和之间的回溯点
};

const bfsVisit = (
    startVertex: string | number = null,
    adjList: Map<string | number, Array<string | number>>,
    color: { [key: string]: Colors },
    distances: { [key: string]: number },
    predecessors: { [key: string]: string | number },
) => {
    const queue: Queue<string | number> = new Queue<string | number>(); // 待访问列表是队列结构的
    color[startVertex] = Colors.GREY; // 开始点只会被访问一次，所以要事先置为灰色，后面被访问完就置为黑色
    queue.enqueue(startVertex); // 开始点

    while (!queue.isEmpty()) { // 直到队列为空才结束
        const u: string | number = queue.dequeue(); // 队列最前端取一个，追踪这个顶点，即第二次访问
        const neighbors: Array<string | number> = adjList.get(u); // 它所有邻接顶点
        for (let i = 0, nl = neighbors.length; i < nl; i ++) { // 遍历所有邻接顶点
            const w: string | number = neighbors[i];
            if (color[w] === Colors.WHITE) { // 当前邻接顶点是白色（没被访问过）才被加到待访问列表
                predecessors[w] = u; // 回溯点自然是u
                distances[w] = distances[u] + 1; // u的距离上加1即可
                color[w] = Colors.GREY; // 白色变为灰色，被访问一次
                queue.enqueue(w); // 入队列（队列尾部），等待第二次访问
            }
        }
        color[u] = Colors.BLACK; // 完全被探索完，变为黑色
    }
};
